// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef MEDIA_FILTERS_SOURCE_BUFFER_RANGE_H_
#define MEDIA_FILTERS_SOURCE_BUFFER_RANGE_H_

#include <stddef.h>

#include <map>

#include "base/callback.h"
#include "base/macros.h"
#include "base/memory/ref_counted.h"
#include "media/base/stream_parser_buffer.h"

namespace media {

// Helper class representing a range of buffered data. All buffers in a
// SourceBufferRange are ordered sequentially in decode timestamp order with no
// gaps.
class SourceBufferRange {
public:
    // Returns the maximum distance in time between any buffer seen in this
    // stream. Used to estimate the duration of a buffer if its duration is not
    // known.
    typedef base::Callback<base::TimeDelta()> InterbufferDistanceCB;

    typedef StreamParser::BufferQueue BufferQueue;

    // Policy for handling large gaps between buffers. Continuous media like
    // audio & video should use NO_GAPS_ALLOWED. Discontinuous media like
    // timed text should use ALLOW_GAPS because large differences in timestamps
    // are common and acceptable.
    enum GapPolicy {
        NO_GAPS_ALLOWED,
        ALLOW_GAPS
    };

    // Return the config ID for the buffer at |timestamp|. Precondition: callers
    // must first verify CanSeekTo(timestamp) == true.
    int GetConfigIdAtTime(DecodeTimestamp timestamp);

    // Return true if all buffers in range of [start, end] have the same config
    // ID. Precondition: callers must first verify that
    // CanSeekTo(start) ==  CanSeekTo(end) == true.
    bool SameConfigThruRange(DecodeTimestamp start, DecodeTimestamp end);

    // Sequential buffers with the same decode timestamp make sense under certain
    // conditions, typically when the first buffer is a keyframe. Due to some
    // atypical media append behaviors where a new keyframe might have the same
    // timestamp as a previous non-keyframe, the playback of the sequence might
    // involve some throwaway decode work. This method supports detecting this
    // situation so that callers can log warnings (it returns true in this case
    // only).
    // For all other cases, including more typical same-DTS sequences, this method
    // returns false. Examples of typical situations where DTS of two consecutive
    // frames can be equal:
    // - Video: VP8 Alt-Ref frames.
    // - Video: IPBPBP...: DTS for I frame and for P frame can be equal.
    // - Text track cues that start at same time.
    // Returns true if |prev_is_keyframe| and |current_is_keyframe| indicate a
    // same timestamp situation that is atypical. False is returned otherwise.
    static bool IsUncommonSameTimestampSequence(bool prev_is_keyframe,
        bool current_is_keyframe);

    // Creates a source buffer range with |new_buffers|. |new_buffers| cannot be
    // empty and the front of |new_buffers| must be a keyframe.
    // |range_start_time| refers to the starting timestamp for the coded frame
    // group to which these buffers belong.
    SourceBufferRange(GapPolicy gap_policy,
        const BufferQueue& new_buffers,
        DecodeTimestamp range_start_time,
        const InterbufferDistanceCB& interbuffer_distance_cb);

    ~SourceBufferRange();

    // Appends |buffers| to the end of the range and updates |keyframe_map_| as
    // it encounters new keyframes.
    // If |new_buffers_group_start_timestamp| is kNoDecodeTimestamp(), then the
    // first buffer in |buffers| must come directly after the last buffer in this
    // range (within the fudge room).
    // If |new_buffers_group_start_timestamp| is set otherwise, then that time
    // must come directly after the last buffer in this range (within the fudge
    // room). The latter scenario is required when a muxed coded frame group has
    // such a large jagged start across tracks that its first buffer is not within
    // the fudge room, yet its group start was.
    void AppendBuffersToEnd(const BufferQueue& buffers,
        DecodeTimestamp new_buffers_group_start_timestamp);
    bool CanAppendBuffersToEnd(
        const BufferQueue& buffers,
        DecodeTimestamp new_buffers_group_start_timestamp) const;

    // Appends the buffers from |range| into this range.
    // The first buffer in |range| must come directly after the last buffer
    // in this range.
    // If |transfer_current_position| is true, |range|'s |next_buffer_index_|
    // is transfered to this SourceBufferRange.
    // Note: Use these only to merge existing ranges. |range|'s first buffer
    // timestamp must be adjacent to this range. No group start timestamp
    // adjacency is involved in these methods.
    void AppendRangeToEnd(const SourceBufferRange& range,
        bool transfer_current_position);
    bool CanAppendRangeToEnd(const SourceBufferRange& range) const;

    // Updates |next_buffer_index_| to point to the Buffer containing |timestamp|.
    // Assumes |timestamp| is valid and in this range.
    void Seek(DecodeTimestamp timestamp);

    // Updates |next_buffer_index_| to point to next keyframe after or equal to
    // |timestamp|.
    void SeekAheadTo(DecodeTimestamp timestamp);

    // Updates |next_buffer_index_| to point to next keyframe strictly after
    // |timestamp|.
    void SeekAheadPast(DecodeTimestamp timestamp);

    // Seeks to the beginning of the range.
    void SeekToStart();

    // Finds the next keyframe from |buffers_| starting at or after |timestamp|
    // and creates and returns a new SourceBufferRange with the buffers from that
    // keyframe onward. The buffers in the new SourceBufferRange are moved out of
    // this range. If there is no keyframe at or after |timestamp|, SplitRange()
    // returns null and this range is unmodified. This range can become empty if
    // |timestamp| <= the DTS of the first buffer in this range.
    SourceBufferRange* SplitRange(DecodeTimestamp timestamp);

    // Deletes the buffers from this range starting at |timestamp|, exclusive if
    // |is_exclusive| is true, inclusive otherwise.
    // Resets |next_buffer_index_| if the buffer at |next_buffer_index_| was
    // deleted, and deletes the |keyframe_map_| entries for the buffers that
    // were removed.
    // |deleted_buffers| contains the buffers that were deleted from this range,
    // starting at the buffer that had been at |next_buffer_index_|.
    // Returns true if everything in the range was deleted. Otherwise
    // returns false.
    bool TruncateAt(DecodeTimestamp timestamp,
        BufferQueue* deleted_buffers, bool is_exclusive);
    // Deletes all buffers in range.
    void DeleteAll(BufferQueue* deleted_buffers);

    // Deletes a GOP from the front or back of the range and moves these
    // buffers into |deleted_buffers|. Returns the number of bytes deleted from
    // the range (i.e. the size in bytes of |deleted_buffers|).
    // This range must NOT be empty when these methods are called.
    // The GOP being deleted must NOT contain the next buffer position.
    size_t DeleteGOPFromFront(BufferQueue* deleted_buffers);
    size_t DeleteGOPFromBack(BufferQueue* deleted_buffers);

    // Gets the range of GOP to secure at least |bytes_to_free| from
    // [|start_timestamp|, |end_timestamp|).
    // Returns the size of the buffers to secure if the buffers of
    // [|start_timestamp|, |end_removal_timestamp|) is removed.
    // Will not update |end_removal_timestamp| if the returned size is 0.
    size_t GetRemovalGOP(
        DecodeTimestamp start_timestamp, DecodeTimestamp end_timestamp,
        size_t bytes_to_free, DecodeTimestamp* end_removal_timestamp);

    // Returns true iff the buffered end time of the first GOP in this range is
    // at or before |media_time|.
    bool FirstGOPEarlierThanMediaTime(DecodeTimestamp media_time) const;

    // Indicates whether the GOP at the beginning or end of the range contains the
    // next buffer position.
    bool FirstGOPContainsNextBufferPosition() const;
    bool LastGOPContainsNextBufferPosition() const;

    // Updates |out_buffer| with the next buffer in presentation order. Seek()
    // must be called before calls to GetNextBuffer(), and buffers are returned
    // in order from the last call to Seek(). Returns true if |out_buffer| is
    // filled with a valid buffer, false if there is not enough data to fulfill
    // the request.
    bool GetNextBuffer(scoped_refptr<StreamParserBuffer>* out_buffer);
    bool HasNextBuffer() const;

    // Returns the config ID for the buffer that will be returned by
    // GetNextBuffer().
    int GetNextConfigId() const;

    // Returns true if the range knows the position of the next buffer it should
    // return, i.e. it has been Seek()ed. This does not necessarily mean that it
    // has the next buffer yet.
    bool HasNextBufferPosition() const;

    // Resets this range to an "unseeked" state.
    void ResetNextBufferPosition();

    // Returns the timestamp of the next buffer that will be returned from
    // GetNextBuffer(), or kNoTimestamp if the timestamp is unknown.
    DecodeTimestamp GetNextTimestamp() const;

    // Returns the start timestamp of the range.
    DecodeTimestamp GetStartTimestamp() const;

    // Returns the timestamp of the last buffer in the range.
    DecodeTimestamp GetEndTimestamp() const;

    // Returns the timestamp for the end of the buffered region in this range.
    // This is an approximation if the duration for the last buffer in the range
    // is unset.
    DecodeTimestamp GetBufferedEndTimestamp() const;

    // Gets the timestamp for the keyframe that is after |timestamp|. If
    // there isn't a keyframe in the range after |timestamp| then kNoTimestamp
    // is returned. If |timestamp| is in the "gap" between the value  returned by
    // GetStartTimestamp() and the timestamp on the first buffer in |buffers_|,
    // then |timestamp| is returned.
    DecodeTimestamp NextKeyframeTimestamp(DecodeTimestamp timestamp);

    // Gets the timestamp for the closest keyframe that is <= |timestamp|. If
    // there isn't a keyframe before |timestamp| or |timestamp| is outside
    // this range, then kNoTimestamp is returned.
    DecodeTimestamp KeyframeBeforeTimestamp(DecodeTimestamp timestamp);

    // Returns whether a buffer with a starting timestamp of |timestamp| would
    // belong in this range. This includes a buffer that would be appended to
    // the end of the range.
    bool BelongsToRange(DecodeTimestamp timestamp) const;

    // Returns true if the range has enough data to seek to the specified
    // |timestamp|, false otherwise.
    bool CanSeekTo(DecodeTimestamp timestamp) const;

    // Returns true if this range's buffered timespan completely overlaps the
    // buffered timespan of |range|.
    bool CompletelyOverlaps(const SourceBufferRange& range) const;

    // Returns true if the end of this range contains buffers that overlaps with
    // the beginning of |range|.
    bool EndOverlaps(const SourceBufferRange& range) const;

    // Returns true if |timestamp| is the timestamp of the next buffer in
    // sequence after |buffers_.back()|, false otherwise.
    bool IsNextInSequence(DecodeTimestamp timestamp) const;

    // Adds all buffers which overlap [start, end) to the end of |buffers|.  If
    // no buffers exist in the range returns false, true otherwise.
    bool GetBuffersInRange(DecodeTimestamp start, DecodeTimestamp end,
        BufferQueue* buffers);

    size_t size_in_bytes() const { return size_in_bytes_; }

private:
    typedef std::map<DecodeTimestamp, int> KeyframeMap;

    // Called during AppendBuffersToEnd to adjust estimated duration at the
    // end of the last append to match the delta in timestamps between
    // the last append and the upcoming append. This is a workaround for
    // WebM media where a duration is not always specified.
    void AdjustEstimatedDurationForNewAppend(const BufferQueue& new_buffers);

    // Seeks the range to the next keyframe after |timestamp|. If
    // |skip_given_timestamp| is true, the seek will go to a keyframe with a
    // timestamp strictly greater than |timestamp|.
    void SeekAhead(DecodeTimestamp timestamp, bool skip_given_timestamp);

    // Returns an iterator in |buffers_| pointing to the buffer at |timestamp|.
    // If |skip_given_timestamp| is true, this returns the first buffer with
    // timestamp greater than |timestamp|.
    BufferQueue::iterator GetBufferItrAt(
        DecodeTimestamp timestamp, bool skip_given_timestamp);

    // Returns an iterator in |keyframe_map_| pointing to the next keyframe after
    // |timestamp|. If |skip_given_timestamp| is true, this returns the first
    // keyframe with a timestamp strictly greater than |timestamp|.
    KeyframeMap::iterator GetFirstKeyframeAt(
        DecodeTimestamp timestamp, bool skip_given_timestamp);

    // Returns an iterator in |keyframe_map_| pointing to the first keyframe
    // before or at |timestamp|.
    KeyframeMap::iterator GetFirstKeyframeAtOrBefore(DecodeTimestamp timestamp);

    // Helper method to delete buffers in |buffers_| starting at
    // |starting_point|, an iterator in |buffers_|.
    // Returns true if everything in the range was removed. Returns
    // false if the range still contains buffers.
    bool TruncateAt(const BufferQueue::iterator& starting_point,
        BufferQueue* deleted_buffers);

    // Frees the buffers in |buffers_| from [|start_point|,|ending_point|) and
    // updates the |size_in_bytes_| accordingly. Does not update |keyframe_map_|.
    void FreeBufferRange(const BufferQueue::iterator& starting_point,
        const BufferQueue::iterator& ending_point);

    // Returns the distance in time estimating how far from the beginning or end
    // of this range a buffer can be to considered in the range.
    base::TimeDelta GetFudgeRoom() const;

    // Returns the approximate duration of a buffer in this range.
    base::TimeDelta GetApproximateDuration() const;

    // Keeps track of whether gaps are allowed.
    const GapPolicy gap_policy_;

    // An ordered list of buffers in this range.
    BufferQueue buffers_;

    // Maps keyframe timestamps to its index position in |buffers_|.
    KeyframeMap keyframe_map_;

    // Index base of all positions in |keyframe_map_|. In other words, the
    // real position of entry |k| of |keyframe_map_| in the range is:
    //   keyframe_map_[k] - keyframe_map_index_base_
    int keyframe_map_index_base_;

    // Index into |buffers_| for the next buffer to be returned by
    // GetNextBuffer(), set to -1 before Seek().
    int next_buffer_index_;

    // If the first buffer in this range is the beginning of a coded frame group,
    // |range_start_time_| is the time when the coded frame group begins. This is
    // especially important in muxed media where the first coded frames for each
    // track do not necessarily begin at the same time.
    // |range_start_time_| may be <= the timestamp of the first buffer in
    // |buffers_|. |range_start_time_| is kNoDecodeTimestamp() if this range does
    // not start at the beginning of a coded frame group, which can happen by
    // range removal or split when we don't have a way of knowing, across
    // potentially multiple muxed streams, the coded frame group start timestamp
    // for the new range.
    DecodeTimestamp range_start_time_;

    // Called to get the largest interbuffer distance seen so far in the stream.
    InterbufferDistanceCB interbuffer_distance_cb_;

    // Stores the amount of memory taken up by the data in |buffers_|.
    size_t size_in_bytes_;

    DISALLOW_COPY_AND_ASSIGN(SourceBufferRange);
};

} // namespace media

#endif // MEDIA_FILTERS_SOURCE_BUFFER_RANGE_H_
